package 剑指Offer.简单;

import java.util.Arrays;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n)。
 *
 *  
 *
 * 示例1:
 *
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author caihe
 * @date 2022/8/25 9:01
 */
public class _42连续子数组的最大和 {

    /**
     * 动态规划
     * 
     * dp[i] 以nums[i]元素结尾的连续子数组的最大和
     * dp[i-1]<0的时候 对后续的和产生了负贡献 dp[i-1]+nums[i]产生的和还没有nums[i]本身大
     * 
     *  - dp[i-1]<0 时， dp[i] = nums[i];
     *  - dp[i+1]>0 时， dp[i] = nums[i] + dp[i+1]
     * 
     * 初始状态 - dp[0] = nums[0] 
     * 返回值 返回dp列表中最大值 - 即连续子数组中最大和
     */
    public int maxSubArray(int[] nums) {
        int maxVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 利用nums本身存储dp结果
            // dp[i-1]大于0就加 小于0就不产生影响
            nums[i] += Math.max(nums[i- 1], 0);
            maxVal = Math.max(maxVal, nums[i]);
        }
        return maxVal;
    }

    /**
     * 前缀和思想
     * 
     */
    public int maxSubArray_v2(int[] nums) {
        // 前缀总和
        int preSum = 0;
        // 记录数组中产生的最小值
        int minSum = 0;
        int res = Integer.MIN_VALUE;
        for (int num : nums) {
            // 一直累加
            preSum += num;
            // 获取累计后的数 减 累加过程中最小的数
            res = Math.max(res, preSum - minSum);
            // 
            minSum = Math.min(preSum, minSum);
        }
        return res;
    }
    
    
}
